Noncommutative variables

Adapted from: Examples 2.11 and 2.2 of [BKP16]

[BKP16] Sabine Burgdorf, Igor Klep, and Janez Povh. Optimization of polynomials in non-commuting variables. Berlin: Springer, 2016.

Example 2.11

We consider the Example 2.11 of [BKP16] in which the polynomial with noncommutative variables $(x * y + x^2)^2 = x^4 + x^3y + xyx^2 + xyxy$ is tested to be sum-of-squares.

using DynamicPolynomials
@ncpolyvar x y
p = (x * y + x^2)^2

\[ x^{4} + x^{3}y + xyx^{2} + xyxy \]

We first need to pick an SDP solver, see here for a list of the available choices.

using SumOfSquares
import CSDP
optimizer_constructor = optimizer_with_attributes(CSDP.Optimizer, MOI.Silent() => true)
model = Model(optimizer_constructor)
con_ref = @constraint(model, p in SOSCone())

optimize!(model)

We see that both the monomials xy and yx are considered separately, this is a difference with the commutative version.

certificate_basis(con_ref)

MonomialBasis{DynamicPolynomials.Monomial{false}, DynamicPolynomials.MonomialVector{false}}(DynamicPolynomials.Monomial{false}[x², xy])

We see that the solution correctly uses the monomial xy instead of yx. We also identify that only the monomials x^2 and xy would be needed. This would be dectected by the Newton chip method of [Section 2.3, BKP16].

gram_matrix(con_ref).Q

2×2 SymMatrix{Float64}:
 1.0  1.0
 1.0  1.0

When asking for the SOS decomposition, the numerically small entries makes the solution less readable.

sos_decomposition(con_ref)

(-1.0000000000000002*x^2 - 1.0000000000000002*x*y)^2 + (-1.0445708785254296e-8*x^2 + 1.0445708785254292e-8*x*y)^2

They are however easily discarded by using a nonzero tolerance:

sos_decomposition(con_ref, 1e-6)

(-1.0000000000000002*x^2 - 1.0000000000000002*x*y)^2

Example 2.2

We consider now the Example 2.2 of [BKP16] in which the polynomial with noncommutative variables $(x + x^{10}y^{20}x^{10})^2$ is tested to be sum-of-squares.

using DynamicPolynomials
@ncpolyvar x y
n = 10
p = (x + x^n * y^(2n) * x^n)^2

using SumOfSquares
model = Model(optimizer_constructor)
con_ref = @constraint(model, p in SOSCone())

optimize!(model)

Only two monomials were considered for the basis of the gram matrix thanks to the Augmented Newton chip method detailed in [Section 2.4, BKP16].

certificate_basis(con_ref)

gram_matrix(con_ref).Q

sos_decomposition(con_ref, 1e-6)

(-1.0000000000000002*x^10*y^20*x^10 - 1.0000000000000002*x)^2

This page was generated using Literate.jl.